/*
 * @lc app=leetcode.cn id=45 lang=cpp
 *
 * [45] 跳跃游戏 II
 */

// @lc code=start
class Solution
{
public:
    int jump(vector<int> &nums)
    {
        //这道题我也不知道到底算不算贪心？
        //思路就是第一步最大覆盖范围为l1 如果没到终点 l1内的点都可以第二次起跳 直到终点
        //同样应该可以用动态规划左做 插个眼
        int res = 0;
        int start = 0; //每一步开始区间
        int end = 1;   //左闭右开区间
        while (end < nums.size())
        {
            int maxnum = 0; //这一步最多覆盖距离
            for (int i = start; i < end; i++)
            {
                maxnum = max(maxnum, nums[i] + i);
            }
            start = end;
            end = maxnum + 1;
            res++;
        }
        return res;
    }
};
// @lc code=end
